static const int N = 10005, M = 1005;
double A[N][M],b[N],c[M],v;
static const double eps=1e-8;
static const double inf = 1e18;
int n, m;

void Pivot(int l,int e) {  
	b[l] /= A[l][e];  
	for(int i=1;i<=n;i++)  
		if(i!=e) A[l][i]/=A[l][e];  
	A[l][e]=1/A[l][e];  
	for(int i=1;i<=m;i++)  
		if(i!=l&&fabs(A[i][e])>eps) {  
			b[i]-=A[i][e]*b[l];  
			for(int j=1;j<=n;j++)  
				if(j!=e)  
					A[i][j]-=A[i][e]*A[l][j];  
			A[i][e]=-A[i][e]*A[l][e];  
		}  
	v+=c[e]*b[l];  
	for(int i=1;i<=n;i++)  
		if(i!=e) c[i]-=c[e]*A[l][i];  
	c[e]=-c[e]*A[l][e];  
}  

double Simplex() {  
	int i,l,e; v = 0;
	while(1) {  
		for(i=1;i<=n;i++)  
			if(c[i]>eps) break;  
		if((e=i)==n+1) return v;  
		double temp=inf;  
		for(i=1;i<=m;i++)  
			if(A[i][e]>eps && b[i]/A[i][e]<temp)
				temp=b[i]/A[i][e],l=i;  
		if(temp==inf) return inf;  
		Pivot(l,e);  
	}  
}  
